package summary;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/11 13:24
 * https://leetcode-cn.com/problems/last-stone-weight-ii/
 */
public class Title1049 {

    /** 看成0-1背包问题,不用关注拿石块的顺序，只用关注结果
     * dp[i]表示重量为j的背包最大能背起的重量
     * 递推公式：dp[i] = Math.min(dp[i],dp[i-nums[i]]+nums[i])
     * 初始化：dp[0] = 0
     * @param stones
     * @return
     */
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int i = 0; i < stones.length; i++) {
            sum += stones[i];
        }
        int target = sum / 2;
        int[] dp = new int[target + 1];
        dp[0] = 0;
        for (int i = 0; i < stones.length; i++) {
            for (int j = target; j >= stones[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - dp[target] * 2;
    }

    public static void main(String[] args) {

    }
}
